Multiversion Reducibility
Definition 5.10 Multiversion Reducibility
A (totally ordered) multiversion history $ m is multiversion reducibile if it can be transformed into a serial monoversion history by a finite sequence of transformation steps, each of which exchanges the order of two adjacent steps, (i.e., steps $ p, q with $ p < qsuch that $ o < p or $ q < ofor all other steps $ o) but without reversing the ordering of a multiversion conflict (i.e. $ rw) pair.
これと 以下の定理を組み合わせる．
Theorem 5.5
A multiversion history is multiversion reducible iff it is multiversion conflict serializable.
つまりMCSR == Multiversion Reducible. Multiversion Reducibilityも同じく，タプルごとの半順序のみでMCSRなアルゴリズムを実装することを可能にする．
あとはどのようなペアも入れ替えてHistoryを作っても，Serializable
具体例
$ r_j(x_i) <_m w_k(x_k)の入れ替えを禁じる，ということを説明する．
以下のヒストリを考える
$ H = w_i(x)r_j(x)w_k(x): serial histoy
$ m = w_i(x_i) r_j(x_i) w_k(x_k): multiversion history
このとき，$ H \sim m. $ mはMultiversion Reducible.
$ m' = w_i(x_i) r_j(x_i) w_j(x_j) w_k(x_k)
のように$ T_jがRead Modify Writeでも， $ w_j(x_jと$ w_k(x_k)はCommutativeなので，$ m' \sim m \sim H.
The equivalent serial monoversion history cannot simply be derived by topologically sorting the graph.
Further information is needed: version order.
MCSR(Multiversion Reducible)であれば，$ rwのグラフが必ずacyclicだが，これのみではSerialization Orderを決定できない．
前述した$ mならびに$ m'にはVersion Orderの指定がない．
Multiversion Schedule $ mにあるVersion Orderが与えられたとき，MVSGが非循環ならMVSRというルールは変わらない．
なので，Version Orderを決定するという処理は依然として必要．
しかし，Multiversion Reducibleなら，$ MCSR \subset MVSRより，「MVSGが非循環になるVersion Orderは必ず存在する」ことを保証できる．
Not MCSR HistoryだとSerializableなVersion Orderは存在しえないかもしれない例
$ m = w_l(x_l) r_i(x_l) r_j(y_0) w_j(x_j) w_i(y_i)
これは Not MCSR, Not Multiversion Reducible.
$ rwpair を入れ替えることなしに，Serial Historyを作れない．
が，これは$ x_j << x_l, y_0 \ll y_iのVersion OrderでMVSR.
$ T_j \to T_l \to T_iでtoposort可能なMVSGが得られる．
Multiversion Conflictの意味
Serial Historyでは直前のWrite stepの値を読む．
Multiversion Historyでは，「Historyにおいて前にある($ <_mな)write stepの値を読む」．
Multiversion Historyにおける w-r の命令順序を入れ替えると，「読めるVersionが減る」．
Multiversion Historyにおける r-wの命令順序を入れ替えると，「読めるVersionが増える」．
r-wの全順序を揃えることで，全トランザクションが「読みうるVersion」を単調減少にできる．
どのように命令列を入れ替えても，各トランザクションの読みうるVersionは減っていくだけになる．
Serial HistoryのMVSGを描いたときに，「読めるVersionが減る」というのは，$ w-rのエッジのsinkが変わる，というふうに言い換えられる．
このとき，元のグラフがacyclicなら，$ w-rのsinkが変わるだけでは，cyclicにできない．(要証明)
なので，同じVersion Orderを使えば，少なくともMVSRであることは保証できる．